#include "string_array.h"
//测试
using namespace std;

//构造字符串
myStr::myStr(const char* ch) {
    next = new int; nextVal = new int;
    int i = 0;
    while (ch[i] != '\0')
        ch[i++];
    data = new char[i];
    length = i;
    while (i--)data[i] = ch[i];
}
myStr::myStr(const myStr&s) {
    next = new int; nextVal = new int;
    data = new char[s.length];
    int i = s.length; length = s.length;
    while (i--)
        data[i] = s.data[i];
}

//销毁字符串
myStr::~myStr() {
    length = 0;
    delete data; data = NULL;
    delete next; next = NULL;
    delete nextVal; nextVal = NULL;
}
//求next数组
void myStr::kmp_next() {
    next = new int[length];
    next[0] = 0;
    if (length > 1)
        next[1] = 1;
    for (int i = 2; i < this->length; i++) {
        int j = -1;
        int p;
        for (p = i - 1; p >= 1; p--) {
            int g = 0;
            for (int w = 0; w < p; w++) {
                if (data[w] == data[i - p + w])g++;
            }
            if (g == p)break;
        }
        next[i] = p + 1;
    }
}
//求nextval矩阵
void myStr::kmp_nextVal() {
    nextVal= new int[length];
    nextVal[0] = 0;
    for (int i = 1; i < this->length; i++) {
        nextVal[i] = 0;
        char x, y;
        x = data[i];
        y = data[next[i] - 1];
        if (x != y)nextVal[i] = next[i];
        else nextVal[i] = nextVal[next[i] - 1];
    }
}

//串的替换
bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V) {
    int i, num;
    for (i = start-1; i < S.length; i++)
    {
        num = 0;
        for (int j = 0; j < T.length; j++)
        {
            if (S.data[i + j] == T.data[j])num++;
            else break;
        }
        if (num == T.length)break;
    }
    if (i == S.length)return 0;
    int j = i + 1, vl = V.length, sl = S.length;
    char* ch = S.data;
    S.length = S.length - T.length + V.length;
    S.data = new char[S.length];
    for (j = 0; j < i; j++)
        S.data[j] = ch[j];
    for (j = 0; j < vl; j++)
        S.data[i + j] = V.data[j];
    j = j + i;
    for ( i ; i < sl; i++)
        S.data[j++] = ch[i + T.length];
    return 1;
}
//查找子串
int simpleMatch(const myStr& S, const myStr& T) {
    int i, num;
    for (i = 0; i < S.length; i++)
    {
        num = 0;
        for (int j = 0; j < T.length; j++)
        {
            if (S.data[i + j] == T.data[j])num++;
            else break;
        }
        if (num == T.length)break;
    }
    if (i == S.length)return -1;
    else return i + 1;
}
//KPM查找子串
int kmpMatch(const myStr& S, const myStr& T) {
    myStr S1 (S);
    S1.kmp_next();
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.data[i - 1] == T.data[j - 1]) { i++; j++; }
        else j = S1.next[j - 1];
    }
    if (j > T.length)return i - T.length;
    else return -1;
}
//输出字符串
void myStr::print() {
    for (int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}
//输出next数组
void myStr::printNext() {
    for (int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}
//输出nextVal数组
void myStr::printNextVal() {
    for (int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

//初始化矩阵
myMatrix::myMatrix() {
    rowNum = 0; colNum = 0; nodeNum = 0;
    nodeList = new matrixNode;
}
myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* data) {
    rowNum = rNum; colNum = cNum; nodeNum = nNum;
    nodeList = new matrixNode[nNum];
    int i = 0, k = 0;
    while (i < nNum * 3)
    {
        nodeList[k].row = data[i++];
        nodeList[k].col = data[i++];
        nodeList[k++].value = data[i++];
    }
    for (int i = 0; i < nodeNum; i++) {
        int min = i;
        for (int j = i + 1; j < nodeNum; j++)
            if (nodeList[j].row < nodeList[min].row)
                min = j;
            else if (nodeList[j].row == nodeList[min].row)
                if (nodeList[j].col < nodeList[min].col)
                    min = j;
        swap(nodeList[i], nodeList[min]);
    }
}
//销毁矩阵
myMatrix::~myMatrix() {
    rowNum = 0; colNum = 0; nodeNum = 0;
    delete nodeList; nodeList = NULL;
}
//倒置矩阵
void myMatrix::FastTransposeSMatrix(myMatrix& T) {
    T.rowNum = colNum; T.colNum = rowNum; T.nodeNum = nodeNum;
    T.nodeList = new matrixNode[nodeNum];
    if (nodeNum) {
        int i = 0, col, p;
        for ( col = 1; col < colNum; col++)
            for ( p = 0; p < nodeNum; p++)
                if (nodeList[p].col==col)
                {
                    T.nodeList[i].col = nodeList[i].row;
                    T.nodeList[i].row = nodeList[i].col;
                    T.nodeList[i].value = nodeList[i].value;
                    i++;
                }
    }
}
//输出稀疏矩阵
void myMatrix::printMatrix() {
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for (int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
